//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
// Related Topics 深度优先搜索 动态规划 回溯算法 
// 👍 754 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.*;

public class PalindromePartitioning {
    public static void main(String[] args) {

        Solution solution = new PalindromePartitioning().new Solution();
//        System.out.println(solution.huiwen("abba"));
        System.out.println(solution.partition("aab"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<String>> res = new ArrayList<>();
        private LinkedList<String> path = new LinkedList<>();
        private Map<String,Boolean> visit = new HashMap<>();
        private int count;

        public List<List<String>> partition(String s) {
            dfs(s,0,s.length());
            return res;
        }

        public void dfs(String s, int start, int end) {
            if (count==s.length()) {
                res.add((List<String>) path.clone());
            }
            for (int i = start; i < end+1; i++) {
                for (int j = i; j < end+1; j++) {
                    if (i==j || !huiwen(s.substring(i, j),i,j)) {
                        continue;
                    }
                    path.addLast(s.substring(i, j));
                    count+=j-i;
                    dfs(s, j, end);
                    path.removeLast();
                    count-=j-i;
                }

            }
        }

        private boolean huiwen(String substring,int rawI ,int rawJ) {
            int i =0;
            int j = substring.length()-1;
            if (visit.containsKey(rawI+","+rawJ)){
                if (visit.get(rawI+","+rawJ)) {
                    return true;
                }else {
                    return false;
                }
            }else {
                while (i <= j && substring.charAt(i) == substring.charAt(j)) {
                    i++;
                    j--;
                }
                if (i == j || i > j) {
                    visit.put(rawI+","+rawJ,true);
                    return true;
                }
                visit.put(rawI+","+rawJ,false);
                return false;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}